/**************************************************************************
 * shortest_path.h
 *
 * CECS619 Project 3
 *
 * Authors: Max Stoler, Jason Hatton
 * 
 *************************************************************************/

#include <stdio.h>
#include <limits.h>
#include "shortest_path.h"

#define INFINITY (INT_MAX/2)
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)<(b)?(b):(a))

void ShortestPath(Graph *graph)
{
	Graph *g;
	int i,j,k;
	int size = graph->size;
	int a,b,c,d;
	int total,max;

	g = GraphCopy(graph);

	for(i=0; i<size; i++)
	{
		for(j=0; j<size; j++)
		{
			a = GraphGetAdj(g,i,j);
			if(a == 0)
				GraphSetAdj(g,i,j,INFINITY);
		}
	}

	for(i=0; i<size; i++)
		GraphSetAdj(g,i,i,0);

	for(k=0; k<size; k++)
	{
		for(i=0; i<size; i++)
		{
			for(j=0; j<size; j++)
			{
				a = GraphGetAdj(g,i,j);
				b = GraphGetAdj(g,i,k);
				c = GraphGetAdj(g,k,j);
				d = MIN(a,b+c);
				GraphSetAdj(g,i,j,d);
			}
		}
	}

	GraphPrint(g);

	total = 0;
	max = 0;
	for(i=0; i<size; i++)
	{
		for(j=0; j<size; j++)
		{
			a = GraphGetAdj(g,i,j);
			max = MAX(max, a);
			total += a;
		}
	}
	printf("\n");
	printf("Longest Path = %d\n", max);
	printf("Average Path = %f\n", (float)total/(float)(size*size));

	GraphDelete(g);
	return;
}

